#include <iostream>
#include <cstdio>
#include <queue>
#include <string>
using namespace std;
class Matrix
{
    static const int MROW = 110,MCOL = 110;
    public:
    int row,col;
    int map[MROW][MCOL];
    Matrix()
    {
        init();
    }
    void init()
    {
        fill(map[0],map[0]+MROW*MCOL,0);
    }
    Matrix operator *(Matrix &b)
    {
        Matrix t;
        t.row=row; t.col=b.col;
        for(int i=0;i<t.row;i++)
            for(int j=0;j<t.col;j++)
            {
                long long s =  0;
                for(int k=0;k<t.col;k++)
                {
                    s+=(long long)map[i][k]*b.map[k][j];
                }
                t.map[i][j] = s%100000;
            }

        return t;
    }
    Matrix qpow(int n)
    {
        Matrix t ,s ;
        t  = *this;
        s.row = s.col = row;
        for(int i=0;i<row;i++)
            s.map[i][i]=1;
        while(n)
        {
            if(n&1)s = s * t;
            t = t * t;
            n>>=1;
        }
        return s;
    }
};
class Trie
{
    public:
    static const int NEXTN = 4,KMAX = 110;
    class Node
    {
        public:
        int id;
        bool eow;
        Node *next[NEXTN],*fail;
        void init(int id)
        {
            this->id = id;
            eow = false;
            fill(next,next+NEXTN,(Node*)NULL);
            fail = NULL;
        }
    };
    Node *root;
    Node keys[KMAX];
    int idCnt;
    void init()
    {
        idCnt = 0;
        root = newkey();
        for(int i=0;i<NEXTN;i++)
            root->next[i] = newkey();
    }
    Node* newkey()
    {
        keys[idCnt].init(idCnt);
        return &keys[idCnt++];
    }
    int trans(char c)
    {
        switch(c)
        {
            case 'A': return 0;
            case 'T': return 1;
            case 'C': return 2;
            case 'G': return 3;
        }
    }
    void insert(string s)
    {
        Node *p = root;
        for(int i=0,to;i<s.size();i++)
        {
            to = trans(s[i]);
            if(p->next[to]==NULL)
            {
                p->next[to]=newkey();
            }
            p=p->next[to];
            if(i==s.size()-1)p->eow = true;
        }
    }
    void buildAC()
    {
        queue<Node*> q;
        for(int i=0;i<NEXTN;i++)
        {
            q.push(root->next[i]);
            root->next[i]->fail = root;
        }
        while(!q.empty())
        {
            Node *pt;
            pt = q.front(),q.pop();
            for(int i=0;i<NEXTN;i++)if(pt->next[i])
            {
                q.push(pt->next[i]);
                Node *t;
                for(t=pt->fail;!t->next[i];t=t->fail);
                pt->next[i]->fail = t->next[i];
                for(t=pt->fail;1;t=t->fail)
                {
                    if(t->next[i]&&t->next[i]->eow)
                        pt->next[i]->eow=true;
                    if(t==root)break;
                }
            }
        }
    }
    void buildMatrix(Matrix &mt)
    {
        mt.row = mt.col = idCnt;
        mt.init();
        for(int i=0;i<idCnt;i++)
        {
            for(int j=0;j<4;j++)
            {
                Node *p;
                for(p=&keys[i];!p->next[j];p=p->fail);
                if(p->next[j]->eow) continue;
                mt.map[i][p->next[j]->id]=1;
            }
        }
       // mt.print();
    }
};
int main()
{
    int m,n;
    string s;
    Trie tree;
    Matrix mt;
    while(cin>>m>>n)
    {
        tree.init();
        while(m--)
        {
            cin>>s;
            tree.insert(s);
        }
        tree.buildAC();
        tree.buildMatrix(mt);
        mt = mt.qpow(n);
        long long res = 0;
        for(int i=1;i<mt.col;i++)res+=mt.map[0][i];
        cout<<res%100000<<endl;
    }
    return 0;
}
